package 力扣日常刷题.木22一月.第04天0111;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 帅小伙
 * @date 2022/1/11
 * @description
 */
public class Demo09回溯中等组合统计 {



    ArrayList<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates,target,new ArrayList<Integer>(),0);
        return ans;
    }

    void dfs(int[]candidates,int target,ArrayList<Integer> list,int index) {
        if(index == candidates.length)return;
        if(target == 0){
            ans.add(new ArrayList<Integer>(list));
            return;
        }


        dfs(candidates,target,list,index+1);

        if(target - candidates[index] >=0){
            list.add(candidates[index]);
            dfs(candidates,target-candidates[index],list,index);
            list.remove(list.size()-1);
        }

    }

}
